// 反转链表

package Leetcode;

import java.util.Deque;
import java.util.LinkedList;

class Solution206_1 {
    public ListNode reverseList(ListNode head) {
        Deque<ListNode> stack = new LinkedList<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        ListNode result = stack.peek();
        ListNode index = stack.isEmpty() ? null : stack.poll();
        while (!stack.isEmpty()) {
            ListNode node = stack.poll();
            index.next = node;
            index = node;
        }
        index.next = null;
        return result;
    }
}

class Solution206_2 {
    public ListNode reverseList(ListNode head) {
        // 使用头插法
        ListNode pre = new ListNode(0); // 表示新链表的头节点的上一个节点
        ListNode cur = head;
        while (cur != null) {
            ListNode t = cur; // 取出当前节点
            cur = cur.next;
            // 把取出的节点插入到新链表
            t.next = pre.next;
            pre.next = t;
        }
        return pre.next;
    }
}

class Solution206_3 {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode n = head.next;
            head.next = pre;
            pre = head;
            if (n == null)
                return head;
            head = n;
        }
        return null;
    }
}